package stack;

import java.util.Deque;
import java.util.LinkedList;

public class 有效括号_20_32 {
}


class 有效的括号_20 {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;

        char[] cArr = s.toCharArray();
        Deque<Character> stack = new LinkedList<>();
        for (char ci : cArr) {
            char left = getLeft(ci);
            if (left == ' ') {
                stack.push(ci);
            } else {
                if (stack.isEmpty() || stack.pop() != left) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    private char getLeft(char c) {
        switch (c) {
            case ')':
                return '(';
            case ']':
                return '[';
            case '}':
                return '{';
        }
        return ' ';
    }
}


/*LinkedList 是栈
PriorityQueue是堆*/
/**
 * 栈法
 */
class 最长的有效括号_32 {


    //  只有 小括号  ()()(    可以用  (()())  和 )()()) 两个来测试
    //  可以参考官方题解https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
    public int longestValidParentheses_stack(String s) {
        if (s == null || s.length() == 0) return 0;
        Deque<Integer> stack = new LinkedList<>();
        // 栈底始终维护一个  最后一个没有被匹配的右括号的下标   初始值为 -1
        stack.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                // 匹配上了 弹出栈顶元素
                stack.pop();

                // 弹空了 说明 ） 太多了 把-1也弹出来了 没有真正匹配上
                // 更新  最后一个没有被匹配的右括号的下标
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    // 否则更新最大长度
                    maxLen = Math.max(maxLen, i - stack.peek());
                }

            }
        }
        return maxLen;
    }




    /**
     * https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-powcai/
     * 动态规划  因为是连续满足条件的长度  因此定义dp  和 s[i] 的元素有关
     * 只有两种情况   ...()   ...((...))  判断这两种即可  详细分析如下
     * dp[i] 以s[i] 结尾  的有效子串的最大长度
     * i : (  肯定 不能形成有效字串  dp[i] = 0  dp[i] = 0 都不修改数组即可 默认都是0
     * i : )  可能形成有效子串
     * i - 1  : (   看 i - 2  dp[i] = dp[i - 2] + 2 注意越界
     * i - 1  : )   尾部就是 ))  s[i-1] 处最大有效长度为dp[i - 1]
     * 跳回去  到s[i - 1 - dp[i - 1]] 位置   为 )    那么从这个 ) 到  s[i] 处  成 )()()) 这种 构成不了  因此 dp[i] = 0
     * 为 （                            成(()()) 这种      因此dp[i] = dp[i - 1]   +  dp[i - dp[i - 1] - 2]       +           1              +   1     注意越界
     * i - 1处最大有效长度   i - dp[i - 1] - 2处最大有效长度  s[i - dp[i - 1] - 1] 的 (  和  s[i] 的 )
     */
    public static int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;
        int[] dp = new int[s.length()];
        // 一个括号形成不了子串
        dp[0] = 0;
        int res = 0;
        for (int i = 1; i < dp.length; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
                } else {
                    if (i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '(') {
                        dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0);
                    }
                }

            }

            res = dp[i] > res ? dp[i] : res;
        }
        return res;
    }

    public static void main(String[] args) {
        longestValidParentheses("())");
    }
}
